package com.atguigu.sort;

import java.util.Arrays;

public class LSDSort {

    private LSDSort() {
    }

    /***
     * 时间复杂度：O( W * ( N + R) )
     * @param arr
     * @param W
     */
    public static void sort(String[] arr, int W) {
        for (String str : arr) {
            if (str.length() != W) {
                throw new IllegalArgumentException("All Strings' length must be the same. ");
            }
        }

        int R = 256;
        int[] cnt = new int[R];
        int[] index = new int[R + 1];
        String[] temp = new String[arr.length];
        for (int i = W - 1; i >= 0; i--) {
            Arrays.fill(cnt, 0);
            for (String s : arr) {
                cnt[s.charAt(i)]++;
            }
            for (int j = 0; j < R; j++) {
                index[j + 1] = index[j] + cnt[j];
            }
            for (String s : arr) {
                temp[index[s.charAt(i)]] = s;
                index[s.charAt(i)]++;
            }
            System.arraycopy(temp, 0, arr, 0, temp.length);
        }
    }

    public static void main(String[] args) {
        String[] arr = {"BCA", "CAB", "ACB", "BAC", "ABC", "CBA"};
        sort(arr, 3);
        for (String s : arr) {
            System.out.println(s);
        }
    }
}
